The present invention relates to computer systems and, more particularly, to packet-data FIFO buffers designed to facilitate computer-device communications over packet-data channels. A major objective of the present invention is to provide more effective use of a packet-data channel for a given FIFO buffer capacity.
Society has been revolutionized by the widespread availability of personal computers. As personal computers have become more powerful, the range of applications they serve has broadened. Increasing with the range of applications is the variety of peripherals that can be attached to personal computers. Early personal computers provided for a keyboard, a display, mass storage, and a printer. More recently, modems, musical instruments such as MIDI synthesizers, analytical instruments, speakers, televisions, video sources such as camcorders, game controllers such as joysticks, scanners, mice, color calibration equipment, graphics tablets, as well as new types of printers, displays, and mass storage devices, are attached to computers.
Where only a few devices are to be attached, each can have its own dedicated port. However, with the proliferation of computer peripherals, it has become desirable to provide ports that handle many peripherals at once. Various network protocols have been developed that allow many computers and devices to interact with each other. However, more cost-effective solutions are available where the goal is for a single computer to manage many peripheral devices. High-performance solutions include both parallel, e.g., small computers systems interface (SCSI), and serial IEEE 1394 (Firewire) buses. More economical serial buses include the Apple Desktop Bus (ADB), developed by Apple Corporation, and the Universal Serial Bus (USB), jointly developed by Compaq, Digital Equipment Corporation, IBM PC Company, Intel, Microsoft, NEC, and Northern Telecom. Of the more economical external buses, the USB is the most ambitious in terms of the number (127) of devices that can be attached and the varieties (isochronous, asynchronous) of data that can be handled.
A major challenge for external serial buses like the USB is that, while only one data stream can be handled at a time, the user must experience the effect of multiple concurrent data streams. For example, the user should be able to move the display cursor of a continuous controller, e.g., mouse, while a streaming audio-visual presentation is displayed. To provide the impression of concurrency, each data stream is divided into small packets, which can then be time multiplexed. The time multiplexing is governed by the host computer, which polls attached devices one at a time for data. To minimize interruption of other data streams, it is important that a device respond immediately to the polling. Correspondingly, the host computer may send data to a peripheral device, which should be ready to accept the host data immediately.
Data buffers help provide the desired immediacy to external bus communications. Data to be transmitted from a peripheral device can be pre-stored in a buffer so that it is ready for transmission whenever the device is polled by the host computer. A buffer can also be used to accept data as soon as it is transmitted from a host computer. Typically, first-in-first-out (FIFO) buffers are used to preserve the order of the data. A single device can have many FIFOs for both send and receive functions. The USB specification provides for up to 32 FIFOs per peripheral device.
Each data packet includes a number of data words. In the case of USB, the words are eight-bits each, so the words are referred to as bytes. Associated with each data source or destination (sink) within a USB peripheral device is a maximum packet data payload size between 1 and 1023 bytes. Each packet includes a header, referred to as a Packet ID, which indicates the type of packet, a Cyclic Redundancy Check (CRC) error detection code, and an end-of-packet indicator. A CRC code generated by the receiver may be compared to the transmitted CRC code to determine if the data was received without error. If the CRCs disagree, there was an error in the received packet.
If an error is detected, another attempt should be made to transfer the packet. Packet-data FIFOs include means for recreating the state that existed at the start of the erroneous transfer. In the case of a transmission, the transmitted data is saved until the packet is acknowledged, unlike a regular data FIFO buffer that would discard each data word as it is transferred. In the case of reception, an erroneously received data packet is cleared while any previously received valid packets are preserved.
A typical FIFO data buffer can include a write pointer that indicates the FIFO location to which a word is to be written and a read pointer that indicates the FIFO location from which a word is to be read. A packet-data FIFO buffer can also include a first-word pointer that indicates the FIFO memory location of the first word in the packet being transferred. This is the memory location to which one of the other two pointers is to be reset in the event of a failed packet transfer. When a FIFO is receiving data over the external serial bus, the first-word pointer marks the location to which the write pointer is to be reset on a receive error. When a FIFO is transmitting over the external serial bus, the first-word pointer marks the location to which the read pointer is to be reset on a transmit error indicated by the host computer. In effect, the first-word pointer stores the state of the buffer prior to the current data packet transfer.
Buffers with greater capacity are more expensive but offer more effective utilization of the external bus. A packet-data FIFO buffer should at least have the capacity to hold one maximum-sized packet. However, loading a second packet into a one-packet FIFO cannot begin until the first packet has been acknowledged. Thus, the second packet will not be available if a request for it immediately follows acknowledgment.
Intel discloses unidirectional FIFO buffers that hold two packets at a time. Once the first packet is transferred, the second packet is immediately available for transfer. A third packet can be loaded as the second packet is transferred. However it is possible that the third packet will not be completely loaded by the time the second packet is acknowledged. If the Intel design could accommodate FIFOs that handle more than two packets, the potential latencies could be reduced. However, to eliminate the latencies for all possible permutations of packet sizes would require a capacity of many maximum-sized packets. This would be costly method of maximizing bus utilization.
Furthermore, the Intel design requires considerable management overhead on the part of the controller of the incorporating peripheral device. Increasing the number of packets that this design could support would increase the management overhead. This reduces the time the controller can attend to activities, e.g., data generation and processing, other than bus management. Additionally, this overhead makes it very difficult, or even impossible, for a single FIFO to swap between transmission and reception modes in time to service a superseding request. Accordingly, two FIFOs are used when only one needs to be used at a time. What is needed is a packet-data FIFO buffer system that provides more effective utilization of an external bus while minimizing external support requirements so that rapid mode switching is possible and allowing a local controller more time to attend to non-bus related functions.